﻿// 5368. 最短距离.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/5371/

给定一个由 n
 个点 m
 条边构成的无向图。

图中保证无自环，但可能有重边。

点的编号为 1∼n
。

将所有点一共分为 k
 类，其中第 i
 类点的数量为 ci
。

具体来说，按照点的编号顺序，前 c1
 个点为第 1
 类点，接下来 c2
 个点为第 2
 类点，…
，最后 ck
 个点为第 k
 类点。

边的编号为 1∼m
。

第 i
 条边连接点 ui
 和点 vi
，长度为 xi
。

首先，请你判断，本题给出的图是否满足：任意两个同类点之间的最短距离均为 0
。

如果满足，则请你进一步计算，任意两类点之间的最短距离。

输入格式
第一行包含三个整数 n,m,k
。

第二行包含 k
 个整数 c1,c2,…,ck
，输入保证 ∑i=1kci=n
。

接下来 m
 行，每行包含三个整数 ui,vi,xi
。

输出格式
如果本题给出的图不满足任意两个同类点之间的最短距离均为 0
，则输出一行 No 即可。

如果本题给出的图满足任意两个同类点之间的最短距离均为 0
，则首先输出一行 Yes。

随后输出一个 k×k
 的矩阵 d
，具体来说，接下来 k
 行，其中第 i
 行输出 k
 个整数 d[i][1],d[i][2],…,d[i][k]
。

关于矩阵 d
：

d[i][j]
 表示第 i
 类点与第 j
 类点之间的最短距离，如果两类点之间不连通，则 d[i][j]=−1
。
d[i][i]=0
。
数据范围
前 4
 个测试点满足 1≤n≤4
。
所有测试点满足 1≤n≤105
，0≤m≤105
，1≤k≤500
，1≤ci,ui,vi≤n
，0≤xi≤104
。

输入样例1：
4 4 2
1 3
2 3 0
3 4 0
2 4 1
2 1 2
输出样例1：
Yes
0 2
2 0
输入样例2：
3 1 2
2 1
1 2 0
输出样例2：
Yes
0 -1
-1 0
输入样例3：
3 2 2
2 1
1 2 0
2 3 1
输出样例3：
Yes
0 1
1 0
输入样例4：
3 0 2
1 2
输出样例4：
No
*/
int main()
{
    std::cout << "Hello World!\n";
}

 